TNotes.leetcode

Appearance

0812. 最大三角形面积【简单】

0812. 最大三角形面积【简单】 ​

📚 相关资源

1. 📝 题目描述 ​

  • 给你一个由 X-Y 平面上的点组成的数组 points，其中 points[i] = [xi, yi]。
  • 从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。
  • 与真实值误差在 10^-5 内的答案将会视为正确答案。

示例 1：

img

txt
输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出：2.00000
解释：输入中的 5 个点如上图所示，红色的三角形面积最大。

示例 2：

txt
输入：points = [[1,0],[0,0],[0,1]]
输出：0.50000

提示：

  • 3 <= points.length <= 50
  • -50 <= xi, yi <= 50
  • 给出的所有点 互不相同

2. 🎯 s.1 - 暴力枚举 + 向量叉积 ​

js
/**
 * @param {number[][]} points
 * @return {number}
 */
var largestTriangleArea = function (points) {
  const n = points.length
  let maxArea = 0

  // 枚举所有可能的三个点的组合
  for (let i = 0; i < n - 2; i++) {
    for (let j = i + 1; j < n - 1; j++) {
      for (let k = j + 1; k < n; k++) {
        // 使用向量叉积计算三角形面积
        const area = calculateTriangleArea(
          points[i][0],
          points[i][1],
          points[j][0],
          points[j][1],
          points[k][0],
          points[k][1]
        )
        maxArea = Math.max(maxArea, area)
      }
    }
  }

  return maxArea
}

// 使用向量叉积计算三角形面积
// 公式：面积 = 0.5 * |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)|
const calculateTriangleArea = (x1, y1, x2, y2, x3, y3) => {
  return 0.5 * Math.abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
}
  • 时间复杂度：O(n3)，其中 n 是点的数量，需要枚举所有可能的三点组合
  • 空间复杂度：O(1)，只使用了常数个额外变量

3. 🎯 s.2 - 暴力枚举 + 海伦（Heron）公式 ​

js
/**
 * @param {number[][]} points
 * @return {number}
 */
var largestTriangleArea = function (points) {
  const n = points.length
  let maxArea = 0

  // 枚举所有可能的三个点的组合
  for (let i = 0; i < n - 2; i++) {
    for (let j = i + 1; j < n - 1; j++) {
      for (let k = j + 1; k < n; k++) {
        const area = calculateTriangleAreaByHeron(
          points[i],
          points[j],
          points[k]
        )
        maxArea = Math.max(maxArea, area)
      }
    }
  }

  return maxArea
}

// 使用海伦公式计算三角形面积
// 公式：面积 = sqrt(s*(s-a)*(s-b)*(s-c))，其中s为半周长
const calculateTriangleAreaByHeron = (p1, p2, p3) => {
  // 计算三边长度
  const a = Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2))
  const b = Math.sqrt(Math.pow(p2[0] - p3[0], 2) + Math.pow(p2[1] - p3[1], 2))
  const c = Math.sqrt(Math.pow(p3[0] - p1[0], 2) + Math.pow(p3[1] - p1[1], 2))

  // 计算半周长
  const s = (a + b + c) / 2

  // 计算面积

  // ❌ 错误写法：
  // return Math.sqrt(s * (s - a) * (s - b) * (s - c))

  // ✅ 正确写法：
  const val = s * (s - a) * (s - b) * (s - c)
  return Math.sqrt(Math.max(0, val))
}
  • 时间复杂度：O(n3)，需要枚举所有可能的三点组合
  • 空间复杂度：O(1)，只使用了常数个额外变量
  • 注意：最后返回结果需要在开根号前保护精度
js
// 写法 1
return Math.sqrt(s * (s - a) * (s - b) * (s - c))

// 写法 2
const val = s * (s - a) * (s - b) * (s - c)
return Math.sqrt(Math.max(0, val))
  • 写法 1 提交后会报错：
    • img
    • 错误原因很典型 —— Heron（海伦）公式在浮点计算下可能会因为四个因子乘积出现微小的负数，导致 Math.sqrt 得到 NaN。
    • 换句话说 s*(s-a)*(s-b)*(s-c) 在数学上应该 ≥ 0，但在浮点运算中可能变成 -1e-15 之类的值，从而 Math.sqrt 返回 NaN。

Discussions